class Solution(object):
    def minimumTimeRequired(self, jobs, k):
        n = len(jobs)
        left = max(jobs)
        right = sum(jobs)
        def cal(val):
            p = [0] * n
            st = []
            def dfs(index):
                for i in range(index, n):
                    if p[i] == 0:
                        if st and st[-1] + jobs[i] <= val:
                            st[-1] += jobs[i]
                            p[i] = 1
                            flag = dfs(i + 1)
                            if flag:
                                return True
                            p[i] = 0
                            st[-1] -= jobs[i]
                for i in range(n):
                    if p[i] == 0:
                        st.append(jobs[i])
                        p[i] = 1
                        flag = dfs(i + 1)
                        if flag:
                            return True
                        p[i] = 0
                        st.pop()
                if len(st) <= k and all(p):
                    return True
                else:
                    return False
            return dfs(0)
        while left < right:
            mid = (left + right) // 2
            if cal(mid):
                right = mid
            else:
                left = mid + 1
        return left




data = Solution()
# jobs = [1,2,4,7,8]
# k = 2
# print(data.minimumTimeRequired(jobs, k))
jobs = [10001,10002,10003,10004,10005,10006,10007,10008,10009,10010,10011,1000000]
k = 11
print(data.minimumTimeRequired(jobs, k))
